package LeetCodeTask.BinarySearch;

/**
 * 稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，
 * 编写一种方法，找出给定字符串的位置。
 * eg:words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""],
 * s = "ta"
 *输出-1 不存在
 */
public class SparseArraySearch {
    public int findString(String[] words, String s) {
        if(words.length == 1 && words[0].equals(s))
            return 0;

        int i = 0,j = words.length-1;
        while(i<=j){

            while(i < j && words[i].equals("")) i ++;
            while(i < j && words[j].equals("")) j --;
            int mid =(i+j)/2;
            int tmp = mid;
            while(tmp < j && words[tmp].equals("")) tmp ++;

            if(words[mid].compareTo(s)>0){
                j=mid-1;
            }else if(words[mid].compareTo(s)<0){
                i=tmp+1;
            }else{
                return tmp;
            }

        }
        return -1;
    }
}
